import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-08
 * Time:22:15
 */
public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return A;
    }

    public void inorderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTree(root.left);
        System.out.print(root.val + " ");
        inorderTree(root.right);
    }

    //检查两棵树是否相同/相同的树
    //给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上(两棵树一模一样)相同，并且节点具有相同的值，则认为它们相同。
    //结构不同的条件：p != null && q == null || p == null && q!= null
    //如果判断了结构相同，那么判断值是否相同；如果判断了两棵树的节点结构相同且值相同，则开始判断当前节点的左子树是否一样 && 右子树是否一样
    //当p != null && q != null,说明两棵树同时不为空，没有遍历结束，当p == null && q == null,说明两棵树同时为空，遍历结束
    //假设p的节点数为m，q的节点数为n，时间复杂度：O(min(m,n)) - 如果p的节点较少，那它就比q提前走到空，那么整个过程就结束了，因此取两者最小值
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.先判断结构是否相同
        if (p != null && q == null || p == null && q != null) {
            return false;
        }
        //2.上述代码如果没有执行，则说明两个引用 同时为空 或者 同时不为空
        if (p == null && q == null) {
            return true;
        }
        //3.都不为空，判断值是否一样
        if (p.val != q.val) {
            return false;
        }
        //4.都不为空且值一样
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //另一棵树的子树
    //给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false
    //二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
    //思路：1.当前子树和根节点是否一样(tree自身是子树的情况)
    //2.判断子树是不是和当前root的左子树一样
    //3.判断子树是不是和当前root的右子树一样
    //假设root有r个节点，subRoot有s个节点，时间复杂度为：O(r*s) - 两棵二叉树需要同时遍历
    public boolean isSubTree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        //当前的子树subRoot是root自身的情况
        if (isSameTree(root, subRoot)) {
            return true;
        }
        //当前的子树subRoot是root的左子树的情况
        if (isSubTree(root.left, subRoot)) {
            return true;
        }
        //当前子树subRoot是root的右子树的情况
        if (isSubTree(root.right, subRoot)) {
            return true;
        }
        //如果上述的所有情况都不是，说明subRoot不是root的一棵子树
        return false;
        //return isSubTree(root.right,subRoot);//也可以直接简写成这样
    }

    //翻转二叉树
    //给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    //思路：定义一个临时的二叉树节点引用tmp，用于交换左右子树的节点：首先先将根节点root的left和right引用通过tmp交换位置，实现左右子树的翻转，
    //然后root进入左子树，重复上述的步骤将root的left和right通过tmp交换，实现左子树的翻转，最后是进入右子树，重复之前步骤
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        //以下的if语句节省了继续遍历叶子结点的左子树和右子树，因为这些都是null
        if (root.left == null && root.right == null) {
            return root;
        }

        TreeNode tmp = root.left;
        root.left = root.right;
        tmp = root.right;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    //对称二叉树
    //给你一个二叉树的根节点 root ， 检查它是否轴对称。
    //思路：想要判断二叉树是否是轴对称，先判断root根节点的左右子树是否结构一样，如果结构一样，在判断值是否一样，如果一样，再判断：
    //左子树的左树 和 右子树的右树 是否是轴对称 && 右子树的右树 和 左子树的左树 是否是轴对称
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return false;
        }
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
    }

    //平衡二叉树
    //给定一个二叉树，判断它是否是 平衡二叉树(平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。)
    //也就是说，如果一棵树是平衡二叉树，那么它的每棵子树都是平衡二叉树，左右子树的高度差 <=1 ，如果 >2 则不是平衡二叉树
    //思路：遍历当前这棵树的每个节点，求每个节点的左子树和右子树的高度，如果发现 h>2 ,则返回false, && root的左子树是平衡的
    //&& root的右子树也是平衡的
    //方法一：时间复杂度为：O(N^2)
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return Math.abs(leftHeight - rightHeight) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    //方法二：时间复杂度为O(N)
    //思路：在求取左右子树的高度的过程中，顺便也判断左右子树是否平衡，而不是在最后的时候再判断：
    //如果在判断左子树的高度差大于1时，那么左子树的高度leftHeight直接返回一个负数（-1），代表不平衡，就再在需要再判断右子树了；示例：
    //在左子树中，如果左子树的高度leftHeight大于0，并且右子树高度rightHeight大于0，那么就要判断leftHeight-rightHeight的绝对值是否小于等于1，
    //如果不是小于等于1，返回-1，那么最终左子树高度leftHeight接收到的值就是-1，<0,说明左子树不是平衡的，也返回一个-1；
    //如果是rightHeight大于等于0并且高度差小于等于1的，则返回左子树和右子树中的较大的值+1,即返回二叉树的高度。
    //最后再判断高度是否是大于等于0的，如果是，则说明二叉树是平衡二叉树，如果不是，则说明二叉树不是平衡二叉树
    public boolean isBalanced1(TreeNode root) {
        if (root == null) {
            return true;
        }
        //5.最后判断一下二叉树的高度是否大于等于0，如果是，则说明二叉树是平衡二叉树
        return getHeight1(root) >= 0;
    }

    public int getHeight1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //1.递归获得左子树的高度
        int leftHeight = getHeight1(root.left);
        //4.判断此时的leftHeight是否大于0，如果不是返回-1，无需再进行rightHeight的计算
        if (leftHeight < 0) {
            return -1;
        }
        //2.递归获得右子树的高度
        int rightHeight = getHeight1(root.right);
        //3.判断左子树和右子树的高度差是否小于等于1（rightHeight必须大于等于0），如果是，说明是平衡的，返回树的高度，如果不是，返回-1
        if (rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight, rightHeight) + 1;
        } else {
            return -1;
        }
    }

    //二叉搜索树和双向链表
    //输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 空间复杂度O(1)（即在原树上操作），时间复杂度O(n)
    //对于树中的任意一个节点：1.其左子树中所有节点的值都小于该节点的值。2.其右子树中所有节点的值都大于该节点的值。
    //3.其左、右子树也各自都是二叉搜索树。
    //这个性质适用于搜索树中的每一个节点，而不仅仅是根节点。
    //注意:
    //1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
    //2.返回链表中的第一个节点的指针
    //3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
    //思路：根据二叉搜索树的特点，对二叉搜索树进行 中序遍历，会得到一个升序排列的节点值序列
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        ConvertChild(pRootOfTree);//对二叉搜索树进行中序遍历
        //寻找双向链表的头节点
        TreeNode head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }

    public TreeNode prev = null;

    public void ConvertChild(TreeNode root) {
        if (root == null) {
            return;
        }
        ConvertChild(root.left);//root的左子树递归结束之后，此时处于值为1的节点的左子树叶子节点root
        //打印
        //1.将此时的root的前驱/左子树节点指向prev
        root.left = prev;
        //3.如果prev此时不为空null，则将prev的后继/右子树节点指向root
        if (prev != null) {
            prev.right = root;
        }
        //2.然后prev走到root的位置
        prev = root;
        ConvertChild(root.right);
    }

    //二叉树的构建及遍历
    //编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串：
    //ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
    //想要复原出二叉树的形状，要么通过前序遍历序列搭配中序遍历序列得出，要么通过后序遍历序列搭配中序遍历序列得出。无法只是通过其中一种遍历方式
    //得出二叉树的形状，但是，本题中知道空树的位置，因此，可以只通过题目中给出的前序遍历字符串复原出二叉树的形状，因为空节点的标记明确了树的结构，
    //告诉我们哪些节点没有左子树或右子树，从而可以递归地根据前序遍历顺序（根-左子树-右子树）还原二叉树
    //思路：构建二叉树：通过变量 i 遍历字符串，每遍历到的字符，按照 1.先创建根节点 2.创建左子树 3.创建右子树
    //注意：输入的字符串要合理，要符合二叉树的三种遍历方式的逻辑，例如 ABC##DE#GUK##F### 这个字符串是错误的
    public int i;//记录i的实时位置，如果在方法内，则它是临时的变量，每次递归时，它不会保存实时位置，而是重新从字符串的初始位置开始

    public TreeNode createTree(String str) {
        //在方法开始时重置i为0 - 多次调用时的情况
        i = 0;
        return createTreeHelper(str);
    }

    public TreeNode createTreeHelper(String str) {
        TreeNode root = null;
        //防止越界
        if (i >= str.length()) {
            return null;
        }
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTreeHelper(str);
            root.right = createTreeHelper(str);
        } else {
            i++;
        }
        return root;
    }

    //二叉树的最近公共祖先
    //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：“对于有根树 root 的两个节点 p、q，最近公共祖先表示为一个节点 x，
    //满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
    //方法一，思路：当二叉树为空，则返回null；最近公共祖先有四种情况：
    //1.如果节点p或者节点q刚好等于根节点root，则代表root就是p和q的最近公共祖先且深度最大
    //2.如果不是第1种情况，那么先递归遍历root的左子树，寻找是否有节点等于p或者q，接着递归遍历root的右子树，寻找是否有节点等于p或者q：
    //如果 p!=null && q!=null，则说明root依然是p和q的最近公共祖先且深度最大
    //如果 p!=null但是q==null，那么左子树最终返回的leftTree节点就是p和q的最近公共祖先且深度最大
    //如果 p==null但是q!=null，那么右子树最终返回的rightTree节点就是p和q的最近公共祖先且深度最大
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }

        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
        if (leftTree != null && rightTree != null) {
            return root;
        } else if (leftTree != null) {
            return leftTree;
        } else {
            return rightTree;
        }
    }
    //方法二，思路：使用栈实现 - 实例化2个Stack对象，创建一个方法getPath，该方法的作用是将二叉树中等于p或者q的节点及途径路径上的所有节点放入栈中，
    //getPath方法的具体做法：首先先将root节点放入栈中，如果root刚好等于node(p或者q)，则返回true；如果不是，则先递归遍历root的左子树，
    //如果左子树中有节点(p或者q)刚好等于root，则返回true，接着递归遍历右子树，如果右子树中有节点(p或者q)刚好等于root，则返回true；如果在递归
    //遍历左子树或右子树中节点时，没有找到p或者q，那么将此时栈中的栈顶元素出栈，然后返回false。
    //回到lowestCommonAncestor1方法中，此时stackP栈已经存放了二叉树中等于p的节点及途径路径上的所有节点，stackQ中已经存放了二叉树中等于p的
    //节点及途径路径上的所有节点；获取这两个栈的差值size，大的栈将栈中元素出栈size个后，在stackP和stackQ都不为空的情况下，获取一下两个栈各自的
    //栈顶元素，如果相等，则返回其中一个的栈顶元素，该元素即为最近公共祖先且深度最大，如果不相等，则各自将栈的栈顶元素出栈，继续判断，直到两个栈都
    //为空时，则代表没有公共祖先，返回null。
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //1.获取二叉树中等于p或者q的节点及途径路径上的所有节点，放入栈中
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root, p, stackP);
        getPath(root, q, stackQ);
        //2.比较两个栈的大小，大的栈出它们的差值size个节点
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if (sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while (size != 0) {
                stackP.pop();
                size--;
            }
        } else {
            int size = sizeQ - sizeP;
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }
        //3.每次出数据之前，看栈顶元素是否一样，如果一样，返回其中一个的栈顶元素，即为最近公共祖先
        while (!stackP.empty() && !stackQ.empty()) {
            if (stackP.peek() == stackQ.peek()) {
                return stackP.peek();
            } else {
                stackP.pop();
                stackQ.pop();
            }
        }
        //没有最近公共祖先返回null
        return null;
    }
    //node - 栈的节点
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        stack.push(root);

        if (root == node) {
            return true;
        }
        boolean ret = getPath(root.left, node, stack);
        if (ret == true) {
            return true;
        }
        ret = getPath(root.right, node, stack);
        if (ret == true) {
            return true;
        }
        stack.pop();
        return false;
    }

    //根据二叉树创建字符串
    //给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
    //空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
    //输入：root = [1,2,3,4]
    //输出："1(2(4))(3)"
    //解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
    //输入：root = [1,2,3,null,4]
    //输出："1(2()(4))(3)"
    //解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
    //思路：创建一个StringBuilder类对象，用来拼接每次由二叉树节点转化的字符串。在tree2strChild方法中：首先将当前根节点root拼接，开始拼接
    //左子树节点root.left：如果root的左子树不等于null，则先拼接一个"("，然后通过递归将左子树中的左子树left节点拼接，如果left等于null，而且
    //左子树中的右子树right也等于null，则直接返回，如果right不等于null，那么需要将为null的left拼接一个"()"；直到root的左子树全部遍历完成，
    //最后拼接一个")"。  接着开始拼接右子树节点root，right：如果root的右子树不等于null，则先拼接一个"("，然后通过递归将右子树中的右子树right
    //节点拼接，在拼接right之前，会先去递归前面写完的拼接root。left节点，然后再进行right的拼接，这样在拼接right会遇到的情况都包含了；如果right
    //等于null，直接返回即可，直到root的右子树全部遍历完成，最后拼接一个")"。
    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        stringBuilder.append(root.val);

        if (root.left != null) {
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            if (root.right == null) {
                return;
            }else {
                stringBuilder.append("()");
            }
        }

        if (root.right != null) {
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            return;
        }
    }
}
